package com.acwing.partition9;

import java.io.*;

/**
 * @author `RKC`
 * @date 2021/12/4 10:01
 */
public class AC868筛质数 {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s = reader.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        writer.write(primeCount1(n) + "\n");
        writer.flush();
    }

    private static int primeCount3(int n) {
        //线性筛，时间复杂度O(n)
        int[] primes = new int[n + 1];
        boolean[] isNotPrime = new boolean[n + 1];
        int answer = 0;
        //1∼n 之内的任何一个合数一定会被筛掉，而且筛的时候只用最小质因子来筛，然后每一个数都只有一个最小质因子，因此每个数都只会被筛一次，因此线性筛法是线性的。
        for (int i = 2; i <= n; i++) {
            if (!isNotPrime[i]) primes[answer++] = i;
            for (int j = 0; primes[j] <= n / i; j++) {
                //使用最小质因子筛去合数
                isNotPrime[primes[j] * i] = true;
                //枚举到了i的最小质因子
                if (i % primes[j] == 0) break;
            }
        }
        return answer;
    }

    private static int primeCount2(int n) {
        //埃式筛，时间复杂度O(nlog(logn))
        int[] primes = new int[n + 1];
        boolean[] isNotPrime = new boolean[n + 1];
        int answer = 0;
        for (int i = 2; i <= n; i++) {
            if (!isNotPrime[i]) {
                primes[answer++] = i;
                //只用质数项去筛
                for (int j = i + i; j <= n; j += i) isNotPrime[j] = true;
            }
        }
        return answer;
    }

    private static int primeCount1(int n) {
        //朴素筛法，时间复杂度O(nlogn)
        int[] primes = new int[n + 1];
        boolean[] isNotPrime = new boolean[n + 1];
        int answer = 0;
        for (int i = 2; i <= n; i++) {
            //如果当前的数没有被筛过，说明[2, i-1]没有任何一个数是i的因子，因此当前数就是质数
            if (!isNotPrime[i]) primes[answer++] = i;
            //删除当前数的每一个的倍数
            for (int j = i + i; j <= n; j += i) isNotPrime[j] = true;
        }
        return answer;
    }
}
